package 排序; // 定义包名
import java.util.*; // 导入Java工具类

/**
 * 该类用于合并区间。
 * 时间复杂度：O(n log n)，空间复杂度：O(n)
 */
public class merge {
    /**
     * 合并区间。
     * 该方法使用快速排序对区间进行排序，然后遍历区间进行合并。
     * @param nums 表示区间的二维数组
     * @return 合并后的区间数组
     */
    public int[][] mergeInterval(int[][] nums){
        ArrayList<int[]> list = new ArrayList<>(); // 创建一个列表来存储合并后的区间
        quickSort(nums, 0, nums.length - 1); // 对区间进行排序
        // Arrays.sort(nums, (o1, o2) -> o1[0] - o2[0]); // 使用Java内置排序
        for(int[] arr : nums){ // 遍历区间
            int size = list.size(); // 获取列表大小
            if(size > 0 && list.get(size - 1)[1] >= arr[0]){ // 如果当前区间与列表中的最后一个区间重叠
                list.get(size - 1)[1] = Math.max(list.get(size - 1)[1], arr[1]); // 更新最后一个区间的结束值
            }else{ // 如果不重叠
                list.add(arr); // 将当前区间添加到列表中
            }
        }
        return list.toArray(new int[list.size()][]); // 返回合并后的区间数组
    }

    /**
     * 快速排序算法。
     * @param nums 待排序的区间数组
     * @param left 左边界
     * @param right 右边界
     */
    private void quickSort(int[][] nums, int left, int right){
        if(left >= right) return; // 如果左边界大于等于右边界，返回
        int pivot = partition(nums, left, right); // 获取基准元素的位置
        quickSort(nums, left, pivot - 1); // 递归排序左半部分
        quickSort(nums, pivot + 1, right); // 递归排序右半部分
    }

    /**
     * 分区函数，用于快速排序。
     * @param nums 待排序的区间数组
     * @param left 左边界
     * @param right 右边界
     * @return 基准元素的位置
     */
    private int partition(int[][] nums, int left, int right){
        int[] val = nums[left]; // 选择第一个区间作为基准
        while(left < right){ // 当左边界小于右边界时继续循环
            while(left < right && nums[right][0] >= val[0]) right--; // 从右向左找小于基准的区间
            nums[left] = nums[right]; // 将小于基准的区间放到左边
            while(left < right && nums[left][0] <= val[0]) left++; // 从左向右找大于基准的区间
            nums[right] = nums[left]; // 将大于基准的区间放到右边
        }
        nums[left] = val; // 将基准区间放到最终位置
        return left; // 返回基准元素的位置
    }

    /**
     * 主方法，处理输入并输出结果。
     * 该方法从标准输入读取区间数组，并输出合并后的区间。
     * @param args 命令行参数
     */
    public static void main(String[] args) {
        Scanner sc = new Scanner(System.in); // 创建扫描器对象
        int m = sc.nextInt(); // 读取行数
        int n = sc.nextInt(); // 读取列数
        sc.nextLine(); // 读取换行符
        int[][] nums = new int[m][n]; // 创建区间数组
        for(int i = 0; i < m; i++){ // 遍历行
            String[] s = sc.nextLine().split(","); // 读取每行的区间
            for(int j = 0; j < s.length; j++){ // 遍历列
                nums[i][j] = Integer.parseInt(s[j]); // 解析区间
            }
        }
        merge mg = new merge(); // 创建对象
        System.out.println(Arrays.deepToString(mg.mergeInterval(nums))); // 输出合并后的区间
        sc.close(); // 关闭扫描器
    }
}
